#include <iostream>
#include <stack>
#include <queue>
using namespace std;
typedef struct BSTNode{
    int data;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

void InsertBST(BSTree &T, int x)//插入二叉排序树
{
    if(!T)//空树
    {
        BSTree p;
        p = new BSTNode;//新二叉排序树结点
        p->data = x;
        p->lchild = p->rchild = NULL;
        T = p;
    }
    else if(x < T->data)
        InsertBST(T->lchild, x);//小的为左孩子
    else if(x > T->data)
        InsertBST(T->rchild, x);//大的为右孩子
}

void CreateBST(BSTree &T)//建立二叉排序树
{
    T = NULL;
    int x;
    cin>>x;
    while(x != 0)
    {
        InsertBST(T, x);
        cin>>x;
    }
}

void ldroutput(BSTree T)//中序输出二叉排序树
{
    if(T)
    {
        ldroutput(T->lchild);
        cout<<T->data<<" ";
        ldroutput(T->rchild);
    }
}

int SearchBST(BSTree T, int x)//二叉排序树查找
{
    if(!T)
        return 0;
    else if(x == T->data)
        return 1;
    else if(x < T->data)
        return SearchBST(T->lchild, x);
    else
        return SearchBST(T->rchild, x);
}

void DeleteBST(BSTree &T, int x)//二叉排序树删除
{
    BSTNode *p=T, *f=NULL;
    while(p)
    {
        if(x==p->data)
            break;
        f = p;
        if(x<p->data)
            p = p->lchild;
        else
            p = p->rchild;
    }
    if(!p)//没有找到待删除点p
        return;
    BSTNode *q = p;
    if(p->lchild && p->rchild)//左右孩子都有
    {
        BSTNode *s = p->lchild;
        while(s->rchild)//找到左子树中最大的点
        {
            q = s;//q为左子树最大点的前驱
            s = s->rchild;
        }
        p->data = s->data;//替换待删除点的值为左子树最大点的值
        if(q == p)//左子树最大点的前驱q就是待删除点p
            q->lchild = s->lchild;//相当于直接把左子树抬上去，右子树接在左子树最大点的右端
        else
            q->rchild = s->lchild;//s不会有右孩子
        delete s;
        return;
    }
    //此时q=p=要删除的结点，f=该点的前驱
    else if(!p->lchild)//没有左孩子
        p = p->rchild;//右子树直接抬上去
    else if(!p->rchild)//没有右孩子
        p = p->lchild;//左子树直接抬上去
    //此时q记录了原待删除点，p为抬上来的点，f为原待删除点前驱
    if(!f)//前驱为空，原待删除点为根
        T = p;//让抬上来的点为根
    else if(q == f->lchild)//原待删除点位前驱左孩子
        f->lchild = p;//前驱左孩子为新点
    else//原待删除点位前驱右孩子
        f->rchild = p;//前驱右孩子为新点
    delete q;//删除q记录的原待删除点
}

int main()
{
    BSTree T;
    CreateBST(T);//创建二叉排序树
    ldroutput(T);//中序输出二叉排序树
    cout<<endl;
    int k;
    cin>>k;
    if(SearchBST(T, k))
        cout << "该数存在" << endl;//查找k成功
    else
        cout << "该数不存在" << endl;//查找k失败
    cin>>k;
    DeleteBST(T, k);//删除k结点
    ldroutput(T);//中序输出二叉排序树
    cout<<endl;
    return 0;
}